/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package adversarial;

import env.Action;
import env.Tile;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

/**
 *
 * @author user
 */
public class HeuristicBFS{

    private HashMap<Tile, HashMap<Tile, Integer>> SP_distances = new HashMap<Tile, HashMap<Tile, Integer>>();
    
    public int dist_nearest_flag(Tile current, Iterable<Tile> flags) {
        int d = Integer.MAX_VALUE;
        for (Tile flag : flags) {
            int temp = dist_to(flag, current);
            if (temp < d) {
                d = temp;
            }
        }
        return d;
    }

    /**********************************************************************
     **********************************************************************
     * 
     *        hash-map building
     * 
     ***********************************************************************
     ***********************************************************************
     */
    private int dist_to(Tile flag, Tile other) {
        HashMap<Tile, Integer> dist = SP_distances.get(flag);
        if (dist == null) {
            dist = new HashMap<Tile, Integer>();
            SP_distances.put(flag, dist);
            dist.put(flag, 0);
            BFS_extend_from_source(dist, flag);
        }
        Integer ans = dist.get(other);
        if (ans == null) {
            //System.err.println("dist_to table of " + flag + " doesn't contain " + other + " which means it's unreachable!");
            return Integer.MAX_VALUE;
        }
        return ans.intValue();
    }


    /**
     * the BFS...
     * @param map the map(Tile -> int)  to improve upon
     * @param source the source, usually map(source)=0 but not neccesary
     * @param str   just for debug
     */
    private static void BFS_extend_from_source(HashMap<Tile, Integer> map, Tile source) {
        Action[] directions = {Action.up, Action.down, Action.left, Action.right};
        LinkedList<Tile> queue = new LinkedList<Tile>();
        HashSet<Tile> closed = new HashSet<Tile>();
        queue.add(source);
        closed.add(source);
        while (!queue.isEmpty()) {
            Tile t = queue.removeFirst();
            //System.out.println("expanding "+t);
            for (Action dir : directions) {
                final Tile n = t.getNeighbor(dir);
                final int dist = map.get(t) + 1;
                if (!n.isWall() && !closed.contains(n)) {
                    if (!map.containsKey(n) || map.get(n) > dist) {
                        map.put(n, dist);
                    }
                    closed.add(n);
                    queue.addLast(n);
//                    if(str!=null)
//                        n.label.setToolTipText("BFS " +str + " from " + row + "," + col + " = " + dist);
                }
            }
        }
    //System.out.println(" BFS for "+str+" is done! d.size=" + map.size());
    }
}
